import java.util.Arrays;

public class Rob2 {
    // 打家劫舍II
    // https://www.nowcoder.com/practice/a5c127769dd74a63ada7bff37d9c5815?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D295
    public int rob (int[] nums) {
        // write code here
        // 分情况讨论，第一家偷和不偷
        // 第一家不偷，那么最后一家可以选择偷和不偷

        // 第一家偷，那么最后一家一定是不偷的
        int n = nums.length;
        if (n == 1) return nums[0];
        return Math.max(rob1(Arrays.copyOfRange(nums, 0, n - 1)),
                rob1(Arrays.copyOfRange(nums, 1, n)));
    }

    private int rob1 (int[] nums) {
        // write code here
        // d[i][0]表示不偷第i家的时候的最高金额，dp[i][1]表示偷第i家时的最高金额
        // dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1], dp[i-2][1])
        // dp[i][1] = max(dp[i-1][0], dp[i-2][0]) + nums[i]
        int[][] dp = new int[nums.length + 2][2];
        for (int i = 2; i < nums.length + 2; i++) {
            dp[i][0] = Math.max(Math.max(dp[i - 1][0], dp[i - 1][1]), dp[i - 2][1]);
            dp[i][1] = Math.max(dp[i - 1][0], dp[i - 2][0]) + nums[i - 2];
        }
        return Math.max(dp[nums.length + 1][0], dp[nums.length + 1][1]);
    }
}
